package com.gorkr.labuladong.data_struct.graph;

import org.junit.jupiter.api.Test;

import java.util.LinkedList;

/**
 * @author gorkr
 * @date 2022/06/10 09:59
 **/
public class M207CourseSchedule {

    private LinkedList[] graph;
    boolean[] visited;
    boolean[] onPath;  // 寻找环的关键
    boolean hasCycle = false;

    private void buildGraph(int numCourses, int[][] prerequisites){
        graph = new LinkedList[numCourses];
//        for (LinkedList g:
//             graph) {
//            g = new LinkedList<Integer>();
//        }
        for (int i = 0; i < graph.length; i++) {
            graph[i] = new LinkedList<Integer>();
        }

        for (int i = 0; i < prerequisites.length; i++) {
            int from = prerequisites[i][1], to = prerequisites[i][0];
            graph[from].add(to);

        }
    }



    public boolean canFinish(int numCourses, int[][] prerequisites) {
        buildGraph(numCourses,prerequisites);
        visited = new boolean[numCourses];
        onPath = new boolean[numCourses];
        for (int i = 0; i < numCourses; i++) {
            traverse(graph,i);
        }
        return !hasCycle;


    }

    private void traverse( LinkedList<Integer>[] graph, int s){
        if(onPath[s]){
            hasCycle = true;
            return;
        }
        if(visited[s] || hasCycle){
            return;
        }
        visited[s] = true;

        onPath[s] = true;
        for (int g :
                graph[s]) {
            traverse(graph, g);
        }
        onPath[s] = false;

    }
    @Test
    public void test(){
        int numCourses = 20;
        int[][] prerequisites = {{0,10},{3,18},{5,5},{6,11},{11,14},{13,1},{15,1},{17,4}};

        System.out.println(canFinish(numCourses, prerequisites));
    }


}
    